/**
 * 67. Add Binary
 * https://leetcode.com/problems/add-binary/
 */
package lc67;

public class Main {
  public static void main(String[] args) {
    String a = "1010", b = "1011";
    String s = new Solution().addBinary(a, b);
    System.out.println(s);
  }
}

class Solution {
  public String addBinary(String a, String b) {
    char[] ac = a.toCharArray();
    char[] bc = b.toCharArray();
    int al = ac.length, bl = bc.length, carry = 0;
    int n = Math.max(al, bl);
    char[] result = new char[n + 1];
    result[0] = 48;
    while (n >= 0) {
      if (--al < 0) ac[++al] = 48;
      if (--bl < 0) bc[++bl] = 48;
      int r = ac[al] + bc[bl] + carry;
      if (r > 97) {
        carry = 1;
        r -= 2;
      } else {
        carry = 0;
      }
      switch (r) {
        case 96:
        result[n] = 48;
        break;
        case 97:
        result[n] = 49;
        default:
        break;
      }
      n--;
    }
    String rs = null;
    if (result[0] == 48) {
      rs = String.copyValueOf(result, 1, result.length - 1);
    } else {
      rs = String.valueOf(result);
    }
    return rs;
  }
}
